package com.nanbei.graph;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassDescription: 深度优先算法
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/1 15:25
 */
public class DFS {

    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        v1.setEdges(Arrays.asList(new Edge(v3), new Edge(v2), new Edge(v6)));
        v2.setEdges(Arrays.asList(new Edge(v4)));
        v3.setEdges(Arrays.asList(new Edge(v4), new Edge(v6)));
        v4.setEdges(Arrays.asList(new Edge(v5)));
        v5.setEdges(Arrays.asList());
        v6.setEdges(Arrays.asList(new Edge(v5)));


        dfsNot(v1);
    }

    //递归调用深度优先算法
    private static void dfs(Vertex v) {
        v.setVisited(true);
        System.out.println(v.getName());
        List<Edge> setEdges = v.getEdges();
        for (Edge edge : setEdges) {

            Vertex linked = edge.getLinked();
            if (!linked.isVisited()) {
                linked.setVisited(true);
                dfs(linked);
            }

        }
    }

    //非递归调用深度优先算法
    private static void dfsNot(Vertex v) {
        LinkedList<Vertex> vertices = new LinkedList<>();
        vertices.push(v);
        while (!vertices.isEmpty()) {
            Vertex pop = vertices.pop();
            System.out.println(pop.getName());
            pop.setVisited(true);
            List<Edge> edges = pop.getEdges();
            for (Edge edge : edges) {
                Vertex vertex = edge.getLinked();
                if (!vertex.isVisited()) {
                    vertices.push(vertex);
                }
            }
        }
    }
}
